#include "bootstrapping.h"

void FastExponentiate(Ciphertext &ciphertext, size_t exponent, Evaluator &evaluator, Ciphertext &result)
{
    // we let result uninitialized until we have to, this is represented by resultIsOne == true
    bool resultIsOne = true;

    // a classical square-and-multiply algorithm
    for (int64_t i = std::numeric_limits<size_t>::digits - 1; i >= 0; --i) {
        if (!resultIsOne) {
            Ciphertext resultMult(evaluator.params, result.Degree() + result.Degree(), evaluator.params->MaxLevel());
            evaluator.Mul(&result, &result, &resultMult, MultiType::ciphertext);
            evaluator.Relinearize(&resultMult, &result);
            LogRelin();
        }
        if (((exponent >> i) & 1) == 1) {
            // multiplying ciphertext to the result here will cause it to be
            // squared exactly i times
            if (!resultIsOne) {
                Ciphertext resultMult(evaluator.params, result.Degree() + ciphertext.Degree(),
                    evaluator.params->MaxLevel());
                evaluator.Mul(&result, &ciphertext, &resultMult, MultiType::ciphertext);
                evaluator.Relinearize(&resultMult, &result);
                LogRelin();
            } else {
                result = ciphertext;
                resultIsOne = false;
            }
        }
    }
}

void Bootstrapper::Bootstrapping(Ciphertext &ciphertext, SecretKey &sk, Context &context)
{
    BootstrappingKey bk;
    CreateBootstrappingKey(sk, bk);
    Ciphertext inCoeffs(&context, 1, context.MaxLevel());
    SlotsToCoeffs(ciphertext, bk, inCoeffs);
    kswitchCounter = 0;
    Ciphertext noisyDec(&context, 1, context.MaxLevel());
    HomomorphicNoisyDecrypt(inCoeffs, bk, noisyDec);
    kswitchCounter = 0;
    Ciphertext in_slots(&context, 1, context.MaxLevel());
    CoeffsToSlots(noisyDec, bk, in_slots);
    kswitchCounter = 0;
    Ciphertext digitExtracted(&context, 1, context.MaxLevel());
    SlotwiseDigitExtract(in_slots, bk, digitExtracted);
    ciphertext = digitExtracted;
}

/*
 * @brief 带噪声的解密，即将明文模数为p的密文转换到明文模数为p^e的密文
 *
 * @param ciphertext 原始密文，噪声很大的密文
 * @param bk 自举用到的密钥结构，里面有对原始密钥加密的一对密文
 * @param destination 转化后的结果
 */
void Bootstrapper::HomomorphicNoisyDecrypt(Ciphertext &ciphertext, BootstrappingKey &bk, Ciphertext &destination) const
{
    uint64_t N = contextChain.TargetContext().N();
    int level = contextChain.TargetContext().MaxLevel();
    Plaintext ciphertextAsPlaintext[2] = {Plaintext(N, level), Plaintext(N, level)};
    contextChain.ConvertCiphertextPlain(ciphertext, ciphertextAsPlaintext);
    BootstrappingEvaluator().lightEncoder->ScaleUp(&ciphertextAsPlaintext[1], &ciphertextAsPlaintext[1]);
    BootstrappingEvaluator().Mul(&bk.encryptedSk, &ciphertextAsPlaintext[1], &destination, MultiType::plaintext);
    BootstrappingEvaluator().lightEncoder->ScaleUp(&ciphertextAsPlaintext[0], &ciphertextAsPlaintext[0]);
    BootstrappingEvaluator().Add(&destination, &ciphertextAsPlaintext[0], &destination);
}

Bootstrapper::Bootstrapper(const Context &bootstrappedContext, std::shared_ptr<const SlotRing> slotRing,
    std::unique_ptr<PolyEvaluator> digitExtractPoly)
    : contextChain(bootstrappedContext, slotRing->Exponent()),
      slotRing(slotRing),
      digitExtractPoly(std::move(digitExtractPoly))
{
    // context compatibility is checked by ContextChain

    if (slotRing->IsDSparse()) {
        traceOp = std::make_unique<SlotwiseTrace>(*slotRing, 0, Log2Exact(slotRing->SlotRank()));
    } else {
        traceOp = std::make_unique<SlotwiseTrace>(*slotRing, 0, Log2Exact(slotRing->SlotRank() / 2));
    }
}
/*
 * @brief 创建自举密钥，包含galois密钥和对原始私钥加密的密文
 *
 * @param sk 原始私钥
 * @param bk 自举密钥存储最后的结果
 * @param allowUninitializedForTest 运行不初始化的测试，为true可以不初始化进行后续操作
 */
void Bootstrapper::CreateBootstrappingKey(SecretKey &sk, BootstrappingKey &bk, bool allowUninitializedForTest) const
{
    assert(coefficientsToSlots != nullptr || allowUninitializedForTest);

    Plaintext skPlain(&contextChain.TargetContext(), contextChain.TargetContext().MaxLevel());

    contextChain.ConvertSkPlain(sk, skPlain);

    SecretKey bootstrappingSk(sk);
    contextChain.ConvertSk(sk, bootstrappingSk);

    KeyGenerator keygen(&(contextChain.TargetContext()));
    PublicKey pk = *keygen.GenPublicKey(&bootstrappingSk);

    PkEncryptor encPk(&contextChain.TargetContext(), &pk);
    Ciphertext encSk(&contextChain.TargetContext(), 1, contextChain.TargetContext().MaxLevel());

    contextChain.TargetEvaluator().lightEncoder->ScaleUp(&skPlain, &skPlain);

    encPk.Encrypt(&skPlain, &encSk);

    std::vector<uint64_t> galoisElements;
    auto digitExtractGaloisElements = digitExtractPoly->GaloisElements();
    galoisElements.insert(galoisElements.end(), digitExtractGaloisElements.cbegin(), digitExtractGaloisElements.cend());

    if (coefficientsToSlots != nullptr) {
        auto linTansformGaloisElements = coefficientsToSlots->GaloisElements();
        galoisElements.insert(galoisElements.end(), linTansformGaloisElements.cbegin(),
            linTansformGaloisElements.cend());
        linTansformGaloisElements = slotsToCoefficients->GaloisElements();
        galoisElements.insert(galoisElements.end(), linTansformGaloisElements.cbegin(),
            linTansformGaloisElements.cend());
    }
    auto traceOpGaloisElements = traceOp->GaloisElements();
    galoisElements.insert(galoisElements.end(), traceOpGaloisElements.cbegin(), traceOpGaloisElements.cend());
    std::sort(galoisElements.begin(), galoisElements.end());
    const auto end = std::unique(galoisElements.begin(), galoisElements.end());
    galoisElements.resize(end - galoisElements.begin());
    std::cout << "creating " << galoisElements.size() << " galois keys" << std::endl;

    GaloisKeys gk(*(GaloisKeys *)keygen.GenGaloisKeys(galoisElements, &bootstrappingSk));
    // RelinearizationKey rk(*(RelinearizationKey *)keygen.GenRelinearizationKey(&bootstrappingSk, 1));
    RelinearizationKey rk(*(static_cast<RelinearizationKey *>(keygen.GenRelinearizationKey(&bootstrappingSk, 1))));

    bk.encryptedSk = encSk;
    bk.gk = std::move(gk);
    bk.rk = std::move(rk);
}

void Bootstrapper::CreateSecretKey(const SecretKey &base_sk, SecretKey &destination) const
{
    contextChain.ConvertSk(base_sk, destination);
}

/*
 * @brief 根据给定的 slotRing 生成 P127PolyEvaluator 对象。
 *
 * @param slotRing slotRing 输入的 SlotRing 对象，包含相关的素数、指数和 N 值等信息。
 * @return std::unique_ptr<PolyEvaluator> 该对象用于在 p=127 和 e=3 的情况下进行多项式评估。
 */
std::unique_ptr<PolyEvaluator> P127TestParametersDigitExtractor(const SlotRing &slotRing)
{
    assert(slotRing.Prime() == 127);
    assert(slotRing.Exponent() == 3);
    assert(slotRing.N() == static_cast<size_t>(1) << 15);
    // 这些值是通过 SAGE 计算并硬编码的；
    // 计算它们需要在有限域上对一个多项式进行因式分解，
    // 然后将结果通过 Hensel 提升到槽环中。
    auto coefficients = { 24040,   1645466, 638722,  310629,  373759,  2040343, 1702357, 1012959, 1330654, 972879,
        85062,   95640,   1896466, 262437,  471266,  1157648, 1336311, 1250040, 622841,  1418600,
        854122,  448430,  1113661, 1076329, 67242,   1020027, 1315226, 1004280, 1890984, 510873,
        1490450, 1664995, 1524537, 719791,  24100,   1731453, 1055624, 163912,  297023,  738333,
        877689,  1121258, 744242,  323617,  1961469, 26253,   1441237, 414438,  1012890, 1345724,
        1094738, 1430813, 1926035, 913882,  1431639, 65384,   702073,  1479718, 930179,  827350,
        213339,  895486,  162364,  1534952, 1261135, 216259,  908225,  1390823, 811185,  773571,
        858483,  116902,  1485134, 95760,   741014,  1719246, 1988449, 843628,  572664,  1474961,
        1689397, 140558,  1288343, 1763928, 90415,   1540960, 694622,  501217,  1840446, 1280873,
        564935,  833880,  1975345, 1308774, 460575,  1378421, 307978,  1778634, 791153,  860979,
        1929116, 1816565, 387144,  780466,  575449,  1541672, 1408027, 1471407, 483539,  1082463,
        1588493, 1881429, 154889,  1767856, 1831001, 555167,  109362,  1552978, 1099674, 1224673,
        1596695, 1518968, 1194351, 155081,  1016728, 96717,   1447799, 1026354 };
    auto indices = { 508, 504, 500, 496, 492, 488, 484, 480, 476, 472, 468, 464, 460, 456, 452, 448, 444, 440, 436,
        432, 428, 424, 420, 416, 412, 408, 404, 400, 396, 392, 388, 384, 380, 376, 372, 368, 364, 360,
        356, 352, 348, 344, 340, 336, 332, 328, 324, 320, 316, 312, 308, 304, 300, 296, 292, 288, 284,
        280, 276, 272, 268, 264, 260, 256, 252, 248, 244, 240, 236, 232, 228, 224, 220, 216, 212, 208,
        204, 200, 196, 192, 188, 184, 180, 176, 172, 168, 164, 160, 156, 152, 148, 144, 140, 136, 132,
        128, 124, 120, 116, 112, 108, 104, 100, 96,  92,  88,  84,  80,  76,  72,  68,  64,  60,  56,
        52,  48,  44,  40,  36,  32,  28,  24,  20,  16,  12,  8,   4,   0 };

    poly element;
    element.resize(512);
    auto indexIt = indices.begin();
    auto coeffIt = coefficients.begin();
    for (; indexIt != indices.end(); ++indexIt, ++coeffIt) {
        element[*indexIt] = *coeffIt;
    }

    poly correctionPoly = { NegateUintMod(63, slotRing.R().scalarMod) };
    size_t log2Exponent = 7;
    return std::make_unique<P127PolyEvaluator>(slotRing, std::move(element), std::move(correctionPoly), log2Exponent);
}

std::unique_ptr<PolyEvaluator> P257TestParametersDigitExtractor(const SlotRing &slotRing)
{
    assert(slotRing.Prime() == 257);
    assert(slotRing.Exponent() <= 3);
    assert(slotRing.N() == static_cast<size_t>(1) << 15);

    auto coefficients = {
        7115559,  16940412, 10241707, 9687872,  7201911,  16887470, 9372790,  1221264,  6275169,  14505080, 8819983,
        14996464, 2406034,  5962143,  7813571,  4005088,  4998650,  3602369,  11674739, 4680484,  11873400, 6752675,
        1240539,  3703884,  1647627,  7878849,  9589184,  539957,   15866923, 1039565,  12618957, 5853175,  864291,
        14372211, 2076817,  5417046,  10501534, 2150062,  16916511, 378561,   4452782,  14364758, 9375360,  16639208,
        8940516,  14678041, 4137957,  12331374, 8516209,  8083421,  9679391,  15762067, 16385806, 1336400,  12016292,
        15577541, 15859213, 16426926, 5464333,  12789605, 8899653,  5446858,  10508216, 16479097, 5746263,  7952608,
        4592847,  8471748,  6331452,  7836187,  6641651,  5342002,  3759910,  15072279, 9800438,  9391808,  12205187,
        14590147, 15296897, 3101990,  6596933,  16169412, 8059777,  16644091, 10922757, 9584558,  6265917,  9342207,
        13596842, 13144779, 14964596, 1520155,  11831766, 5055961,  15309233, 9321390,  169877,   15592961, 6079335,
        11224218, 3642718,  3033371,  4996080,  1847059,  13589646, 2120250,  14092595, 1328433,  16499914, 2382647,
        3506251,  15659781, 8704590,  7576874,  16481924, 13506121, 13873888, 2528623,  2780483,  15841223, 4194240,
        985338,   10900398, 2961925,  1105100,  6917155,  4652471,  3964482,  8487425
    };
    auto indices = { 255, 253, 251, 249, 247, 245, 243, 241, 239, 237, 235, 233, 231, 229, 227, 225, 223, 221, 219,
        217, 215, 213, 211, 209, 207, 205, 203, 201, 199, 197, 195, 193, 191, 189, 187, 185, 183, 181,
        179, 177, 175, 173, 171, 169, 167, 165, 163, 161, 159, 157, 155, 153, 151, 149, 147, 145, 143,
        141, 139, 137, 135, 133, 131, 129, 127, 125, 123, 121, 119, 117, 115, 113, 111, 109, 107, 105,
        103, 101, 99,  97,  95,  93,  91,  89,  87,  85,  83,  81,  79,  77,  75,  73,  71,  69,  67,
        65,  63,  61,  59,  57,  55,  53,  51,  49,  47,  45,  43,  41,  39,  37,  35,  33,  31,  29,
        27,  25,  23,  21,  19,  17,  15,  13,  11,  9,   7,   5,   3,   1,   0 };

    poly element;
    element.resize(256);
    auto indexIt = indices.begin();
    auto coeffIt = coefficients.begin();
    for (; indexIt != indices.end(); ++indexIt, ++coeffIt) {
        element[*indexIt] = *coeffIt % slotRing.R().scalarMod; // reduce
    }

    poly correctionPoly = { 0, NegateUintMod(3, slotRing.R().scalarMod) };
    size_t log2Exponent = 8;
    return std::make_unique<P257CorrectionPolyEvaluator>(slotRing, std::move(element), std::move(correctionPoly),
        log2Exponent);
}

P127PolyEvaluator::P127PolyEvaluator(const SlotRing &slotRing, poly evaluationElement_, poly correctionPoly_,
    size_t log2Exponent_)
    : slotRing(slotRing),
      correctionPoly(std::move(correctionPoly_)),
      log2Exponent(log2Exponent_),
      normOp(slotRing, Log2Exact(slotRing.SlotRank()) - log2Exponent_)
{
    if (evaluationElement_.size() != slotRing.SlotRank()) {
        throw std::invalid_argument("Elements must have SlotRank() coefficients.");
    }
    poly slottedEvaluationElement;
    for (int i = 0; i < slotRing.SlotGroupLen(); i++) {
        PolyAdd(slottedEvaluationElement, slotRing.FromSlotValue(evaluationElement_, i), slotRing.R().scalarMod);
    }
    this->evaluationElement = std::move(slottedEvaluationElement);
}

poly P127PolyEvaluator::operator () (const poly &x) const
{
    throw std::invalid_argument("Unimplemented");
}

/*
 * @brief 同态计算多项式在x处的值，用到Horner方法，只用到多项式为1的情况
 *
 * @param destination 结果密文
 * @param poly 初始明文多项式
 * @param x
 * @param eval
 * @param plainModulus
 */
void NaiveAddPolyEvalInplace(Ciphertext &destination, const poly &poly, Evaluator &eval)
{
    if (poly.size() == 0) {
        return;
    }
    assert(poly[poly.size() - 1] != 0);

    Ciphertext correction;
    bool isCorrectionSet = false;

    vector<uint64_t> currentVector;
    currentVector.resize(eval.params->N());
    Plaintext current(currentVector, eval.params->MaxLevel());
    if (isCorrectionSet) {
        eval.Add(&destination, &correction, &destination);
    }
    current.value->Coeffs[0][0] = poly[0];
    eval.lightEncoder->ScaleUp(&current, &current);
    eval.Add(&destination, &current, &destination);
}
/*
 * @brief 对密文进行数字提取多项式的计算，主要针对p=127的密文
 *
 * @details 该函数实现了针对明文模数p=127的数字提取多项式的同态计算。主要步骤如下:
 * 1. 将评估元素evaluationElement转换为明文多项式
 * 2. 计算(evaluationElement - in)的范数norm，这是修正delta的结果
 * 3. 添加校正多项式correctionPoly的计算结果
 * 4. 计算输入密文的2^log2Exponent次幂
 * 5. 从修正结果中减去幂运算结果得到最终的数字提取结果
 *
 * @param in 输入的密文，其明文模数为p^e
 * @param context 相关的参数上下文，包含明文模数等信息
 * @param eval 对应参数的计算器，用于执行同态运算
 * @param gk 计算过程中用到的galois密钥，主要用于计算范数
 * @param destination 结果密文，存储数字提取的结果
 *
 * @note 该函数是BFV方案中自举操作的核心步骤之一，用于从高次明文模数的密文中提取出低次明文模数的密文
 */
void P127PolyEvaluator::ApplyCiphertext(Ciphertext &in, Context &context, Evaluator &eval, GaloisKeys &gk,
    Ciphertext &destination) const
{
    const uint64_t &plainModulus = context.t;
    Plaintext evaluationElementApply(this->evaluationElement, context.MaxLevel());
    for (int i = 0; i < this->evaluationElement.size(); i++) {
        evaluationElementApply.value->Coeffs[0][i] = this->evaluationElement[i] % plainModulus;
    }
    Ciphertext tmp(eval.params, 1, eval.params->MaxLevel());
    eval.lightEncoder->ScaleUp(&evaluationElementApply, &evaluationElementApply);
    eval.Sub(&in, &evaluationElementApply, &tmp);
    eval.Neg(&tmp, &tmp);
    normOp.ApplyCiphertext(tmp, eval, gk, destination);

    NaiveAddPolyEvalInplace(destination, correctionPoly, eval);

    FastExponentiate(in, static_cast<size_t>(1) << log2Exponent, eval, tmp);
    eval.Sub(&destination, &tmp, &destination);
}

std::vector<uint32_t> P127PolyEvaluator::GaloisElements() const
{
    return normOp.GaloisElements();
}

SlotwiseNorm::SlotwiseNorm(const SlotRing &slotRing, size_t subfieldIndexLog2)
    : slotRing(slotRing), subfieldIndexLog2(subfieldIndexLog2)
{}

poly SlotwiseNorm::operator () (const poly &x) const
{
    poly current = x;
    poly copy;
    for (size_t i = 0; i < Log2Exact(slotRing.SlotRank()) - subfieldIndexLog2; ++i) {
        copy = slotRing.Frobenius_(static_cast<size_t>(1) << i)(current);
        current = PolyMulMod(current, copy, slotRing.R().scalarMod, slotRing.R().polyMod);
    }
    return current;
}
/*
 * @brief 对密文进行数字提取中的相关范数norm计算
 *
 * @param in 输入的密文
 * @param eval 对应参数的计算器
 * @param gk galois变换用到的密钥
 * @param destination 计算后的结果
 */
void SlotwiseNorm::ApplyCiphertext(Ciphertext &in, Evaluator &eval, GaloisKeys &gk, Ciphertext &destination) const
{
    destination.Copy(in.El());
    Ciphertext copy(eval.params, 1, eval.params->MaxLevel());
    for (size_t i = 0; i < Log2Exact(slotRing.SlotRank()) - subfieldIndexLog2; ++i) {
        eval.ApplyGalois(&destination,
            static_cast<uint32_t>(ModExp(slotRing.Prime(), static_cast<size_t>(1) << i, slotRing.IndexMod())),
            gk.GetGaloisKey(
            static_cast<uint32_t>(ModExp(slotRing.Prime(), static_cast<size_t>(1) << i, slotRing.IndexMod()))),
            &copy);
        LogGalois();
        Ciphertext resultMult(eval.params, destination.Degree() + copy.Degree(), eval.params->MaxLevel());
        eval.Mul(&destination, &copy, &resultMult, MultiType::ciphertext);
        eval.Relinearize(&resultMult, &destination);
        LogRelin();
    }
}

std::vector<uint32_t> SlotwiseNorm::GaloisElements() const
{
    std::vector<uint32_t> result;
    for (size_t i = 0; i < Log2Exact(slotRing.SlotRank()) - subfieldIndexLog2; ++i) {
        result.push_back(
            static_cast<uint32_t>(ModExp(slotRing.Prime(), static_cast<size_t>(1) << i, slotRing.IndexMod())));
    }
    return result;
}

/*
 * @brief 数字提取函数，将密文ciphertext(明文模式=p^e)去除噪声，得到密文destination(明文模式=p)
 *
 * @param ciphertext 输入的密文。明文模数为p^e
 * @param bk 自举用到的密钥。主要使用其中的galois密钥
 * @param destination 数字提取后的密文
 */
void Bootstrapper::SlotwiseDigitExtract(Ciphertext &ciphertext, BootstrappingKey &bk, Ciphertext &destination) const
{
    const size_t digitsToRemove = slotRing->Exponent() - 1;
    const size_t highestDigitIndex = slotRing->Exponent() - 1;
    vector<Ciphertext> worktable(digitsToRemove);

    // 添加模数 / 2 以执行四舍五入
    vector<uint64_t> shiftVector;
    shiftVector.resize(contextChain.BaseContext().N());
    Plaintext shift(shiftVector, BootstrappingEvaluator().params->MaxLevel());
    for (size_t i = 0; i < digitsToRemove; ++i) {
        shift.value->Coeffs[0][0] *= slotRing->Prime();
        shift.value->Coeffs[0][0] += slotRing->Prime() / 2;
    }
    destination = ciphertext;
    BootstrappingEvaluator().lightEncoder->ScaleUp(&shift, &shift);
    BootstrappingEvaluator().Add(&destination, &shift, &destination);

    // 初始化worktable表
    for (int i = 0; i < digitsToRemove; i++) {
        worktable[i] = destination;
    }

    for (int i = 0; i < digitsToRemove; i++) {
        const size_t currentIndex = i;
        Ciphertext &current = worktable[i];
        const size_t contextIndex = contextChain.Size() - currentIndex - 1;
        Evaluator &evaluator = contextChain.GetEvaluator(contextIndex);
        const Context &context = contextChain.GetContext(contextIndex);
        RelinearizationKey rk;
        GaloisKeys gk;
        gk = bk.GalKeys();
        rk = bk.RelinKeys();
        evaluator.WithKey(new EvaluationKey(&rk, nullptr));
        Ciphertext tmp(&contextChain.BaseContext(), 1, contextChain.BaseContext().MaxLevel());

        for (int j = 1; j < highestDigitIndex - currentIndex + 1; j++) {
            digitExtractPoly->ApplyCiphertext(current, const_cast<Context &>(context),
                const_cast<Evaluator &>(evaluator), gk, tmp);
            current = tmp;
            if (currentIndex + j < digitsToRemove) {
                BootstrappingEvaluator().Sub(&worktable[currentIndex + j], &tmp, &worktable[currentIndex + j]);
            }
        }
        BootstrappingEvaluator().Sub(&destination, &current, &destination);
    }
}
/*
 * @brief 执行密文从槽到系数的线性变换SlotsToCoeffs
 *
 * @param ciphertext 输入密文，其中明文模数为p
 * @param bk 自举用到的密钥
 * @param destination 线性变换的结果
 */
void Bootstrapper::SlotsToCoeffs(Ciphertext &ciphertext, BootstrappingKey &bk, Ciphertext &destination) const
{
    GaloisKeys baseGk;
    baseGk = bk.GalKeys();
    slotsToCoefficients->ApplyCiphertext(ciphertext, contextChain.GetEvaluator(0), baseGk, destination);
}
/*
 * @brief 执行密文从槽到系数的线性变换SlotsToCoeffs
 *
 * @param ciphertext 输入密文，其中明文模数为p
 * @param bk 自举用到的密钥
 * @param destination 线性变换的结果
 */
void Bootstrapper::CoeffsToSlots(Ciphertext &ciphertext, BootstrappingKey &bk, Ciphertext &destination) const
{
    Ciphertext tmp(ciphertext.CoeffCount(), 1, ciphertext.Level());
    // first we remove all the coefficients "to discard" by applying the trace
    traceOp->ApplyCiphertext(ciphertext, const_cast<Evaluator &>(BootstrappingEvaluator()),
        const_cast<GaloisKeys &>(bk.GalKeys()), tmp);
    // fix the constant factor introduced by trace
    const uint64_t errorFactor = traceOp->field_index() % slotRing->R().scalarMod; // reduce
    const uint64_t correctionFactor = InvMod_(errorFactor, slotRing->R().scalarMod);

    vector<uint64_t> factorVector;
    factorVector.resize(ciphertext.CoeffCount());
    factorVector[0] = correctionFactor;
    Plaintext factor(factorVector, ciphertext.Level());

    BootstrappingEvaluator().Mul(&tmp, &factor, &tmp, MultiType::plaintextRingT);
    coefficientsToSlots->ApplyCiphertext(tmp, const_cast<Evaluator &>(BootstrappingEvaluator()),
        const_cast<GaloisKeys &>(bk.GalKeys()), destination);
}

void Bootstrapper::Initialize()
{
    if (coefficientsToSlots == nullptr) {
        coefficientsToSlots =
            std::make_unique<CompiledSubringLinearTransform>(CompiledSubringLinearTransform::CoeffsToSlots(slotRing));
        slotsToCoefficients =
            std::make_unique<CompiledSubringLinearTransform>(CompiledSubringLinearTransform::SlotsToCoeffs(slotRing));
    }
}

const Context &Bootstrapper::BootstrappingContext() const
{
    return contextChain.TargetContext();
}

/*
 * @brief 测试自举中的编码和解码
 *
 */
void TestEncodeDecode()
{
    std::shared_ptr<SlotRing> slotRing = P257TestParameters();
    SlotRing basicSlotRing = slotRing->ChangeExponent(1);
    Context context(15,
        { 36028797017456641, 36028797014704129, 36028797014573057, 36028797014376449, 36028797013327873,
        36028797013000193, 36028797012606977, 36028797010444289, 36028797009985537, 36028797005856769,
        36028797005529089, 36028797005135873, 36028797003694081, 36028797003563009, 36028797001138177 },
        { 72057594037338113 }, 257, 3.2);
    vector<uint64_t> data;
    PolyAdd(data, slotRing->FromSlotValue({ 1 }, 0), slotRing->R().scalarMod);
    PolyAdd(data, slotRing->FromSlotValue({ 2 }, 1), slotRing->R().scalarMod);
    PolyAdd(data, slotRing->FromSlotValue({ 3 }, 2), slotRing->R().scalarMod);
    PolyAdd(data, slotRing->FromSlotValue({ 4 }, 3), slotRing->R().scalarMod);

    for (size_t i = 0; i < 128; ++i) {
        std::cout << slotRing->ExtractSlotValue(data, i)[0] << std::endl;
    }
}
/*
 * @brief 测试低位提取函数中的多项式计算功能
 *
 */
void TestGaloisPolyEvaluator()
{
    {
        SlotRing slotRing = *P127TestParameters();
        std::unique_ptr<PolyEvaluator> digitExtractor = P127TestParametersDigitExtractor(slotRing);
        Context context(15,
            { 36028797017456641, 36028797014704129, 36028797014573057, 36028797014376449, 36028797013327873,
            36028797013000193, 36028797012606977, 36028797010444289, 36028797009985537, 36028797005856769,
            36028797005529089, 36028797005135873, 36028797003694081, 36028797003563009, 36028797001138177 },
            { 72057594037338113 }, 127 * 127 * 127, 3.2);

        KeyGenerator keygen(&context);
        std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
        SecretKey sk(*tmp.first);
        PublicKey pk(*tmp.second);
        RelinearizationKey rk(*keygen.GenRelinearizationKey(&sk, 1));
        vector<uint64_t> galoisVector;
        for (int i = 0; i < digitExtractor->GaloisElements().size(); i++) {
            galoisVector.push_back(digitExtractor->GaloisElements()[i]);
        }
        GaloisKeys gk(*keygen.GenGaloisKeys(galoisVector, &sk));
        Evaluator eval(&context, new EvaluationKey(&rk, nullptr));

        poly data;
        PolyAdd(data, slotRing.FromSlotValue({ 5 * 127 * 127 + 2 * 127 - 7 }, 0), slotRing.R().scalarMod);
        PolyAdd(data, slotRing.FromSlotValue({ 127 * 127 + 66 }, 1), slotRing.R().scalarMod);
        Plaintext xPlain(data, context.MaxLevel());

        PkEncryptor encryptor(&context, &pk);
        Ciphertext xEnc(&context, 1, context.MaxLevel());

        eval.lightEncoder->ScaleUp(&xPlain, &xPlain);
        encryptor.Encrypt(&xPlain, &xEnc);

        Ciphertext resultEnc(&context, 1, context.MaxLevel());

        digitExtractor->ApplyCiphertext(xEnc, context, eval, gk, resultEnc);

        Decryptor decryptor(&context, &sk);
        Plaintext result(&context, context.MaxLevel());
        decryptor.Decrypt(&resultEnc, &result);
        eval.lightEncoder->ScaleDown(&result, &result);

        poly resultPoly;
        for (int i = 0; i < result.CoeffCount(); i++) {
            resultPoly.push_back(result.value->Coeffs[0][i]);
        }
        resultPoly.resize(slotRing.N());
        poly expected;
        PolyAdd(expected, slotRing.FromSlotValue({ 1822697 /* computed with sage */ }, 0), slotRing.R().scalarMod);
        PolyAdd(expected, slotRing.FromSlotValue({ 66 /* computed with sage */ }, 1), slotRing.R().scalarMod);

        assert(resultPoly == expected);
    }

    {
        SlotRing slotRing = *P257TestParameters();
        std::unique_ptr<PolyEvaluator> digitExtractor = P257TestParametersDigitExtractor(slotRing);
        Context context(15,
            { 36028797017456641, 36028797014704129, 36028797014573057, 36028797014376449, 36028797013327873,
            36028797013000193, 36028797012606977, 36028797010444289, 36028797009985537, 36028797005856769,
            36028797005529089, 36028797005135873, 36028797003694081, 36028797003563009, 36028797001138177 },
            { 72057594037338113 }, slotRing.R().scalarMod, 3.2);

        KeyGenerator keygen(&context);
        std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
        SecretKey sk(*tmp.first);
        PublicKey pk(*tmp.second);
        RelinearizationKey rk(*keygen.GenRelinearizationKey(&sk, 1));
        vector<uint64_t> galoisVector;
        for (int i = 0; i < digitExtractor->GaloisElements().size(); i++) {
            galoisVector.push_back(digitExtractor->GaloisElements()[i]);
        }
        GaloisKeys gk(*keygen.GenGaloisKeys(galoisVector, &sk));
        Evaluator eval(&context, new EvaluationKey(&rk, nullptr));

        poly data;
        PolyAdd(data, slotRing.FromSlotValue({ 5 * 257 * 257 + 6 * 257 - 3 }, 0), slotRing.R().scalarMod);
        Plaintext xPlain(data, context.MaxLevel());

        PkEncryptor encryptor(&context, &pk);
        Ciphertext xEnc(&context, 1, context.MaxLevel());

        eval.lightEncoder->ScaleUp(&xPlain, &xPlain);
        encryptor.Encrypt(&xPlain, &xEnc);

        Ciphertext resultEnc(&context, 1, context.MaxLevel());

        digitExtractor->ApplyCiphertext(xEnc, context, eval, gk, resultEnc);

        Decryptor decryptor(&context, &sk);
        Plaintext result(&context, context.MaxLevel());
        decryptor.Decrypt(&resultEnc, &result);
        eval.lightEncoder->ScaleDown(&result, &result);

        poly resultPoly;
        for (int i = 0; i < result.CoeffCount(); i++) {
            resultPoly.push_back(result.value->Coeffs[0][i]);
        }
        resultPoly.resize(slotRing.N());
        poly expected;
        PolyAdd(expected, slotRing.FromSlotValue({ 15521769 /* computed with sage */ }, 0), slotRing.R().scalarMod);

        assert(resultPoly == expected);
    }
    std::cout << "TestGaloisPolyEvaluator(): success" << std::endl;
}
/*
 * @brief 测试带噪声解密功能
 *
 */
void TestHomomorphicNoisyDecrypt()
{
    {
        std::shared_ptr<const SlotRing> slotRing = P127TestParameters();
        Context context(15,
            { 36028797017456641, 36028797014704129, 36028797014573057, 36028797014376449, 36028797013327873,
            36028797013000193, 36028797012606977, 36028797010444289, 36028797009985537, 36028797005856769,
            36028797005529089, 36028797005135873, 36028797003694081, 36028797003563009, 36028797001138177 },
            { 72057594037338113 }, slotRing->Prime(), 3.2);
        KeyGenerator keygen(&context);
        std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
        SecretKey sk(*tmp.first);
        PublicKey pk(*tmp.second);
        RelinearizationKey rk(*keygen.GenRelinearizationKey(&sk, 1));
        PkEncryptor encryptor(&context, &pk);
        Evaluator evaluator(&context, new EvaluationKey(&rk, nullptr));

        std::vector<uint64_t> data = { 4 };
        data.resize(slotRing->N());
        Plaintext xPlain(data, context.MaxLevel());
        evaluator.lightEncoder->ScaleUp(&xPlain, &xPlain);

        Ciphertext xEnc(&context, 1, context.MaxLevel());
        encryptor.Encrypt(&xPlain, &xEnc);

        poly evaluationElementFake;
        evaluationElementFake.resize(slotRing->SlotRank());
        Bootstrapper bootstrapper(context, slotRing,
            std::make_unique<P127PolyEvaluator, const SlotRing &, poly, poly, size_t>(*slotRing,
            std::move(evaluationElementFake), { 1 }, 7));

        Context bootstrappingContext(bootstrapper.BootstrappingContext());
        SecretKey bootstrappingSk(sk);
        bootstrapper.CreateSecretKey(sk, bootstrappingSk);
        BootstrappingKey bk;
        bootstrapper.CreateBootstrappingKey(sk, bk, true);

        Ciphertext noisyEncX(&bootstrappingContext, 1, bootstrappingContext.MaxLevel());
        bootstrapper.HomomorphicNoisyDecrypt(xEnc, bk, noisyEncX);

        Decryptor decryptor(&bootstrappingContext, &bootstrappingSk);
        Plaintext noisyX(&bootstrappingContext, context.MaxLevel());
        decryptor.Decrypt(&noisyEncX, &noisyX);
        bootstrapper.BootstrappingEvaluator().lightEncoder->ScaleDown(&noisyX, &noisyX);

        auto div_rounded = [&slotRing](uint64_t x) {
            return (x + (slotRing->R().scalarMod / slotRing->Prime() / 2)) % slotRing->R().scalarMod /
                (slotRing->R().scalarMod / slotRing->Prime());
        };
        assert(div_rounded(noisyX.value->Coeffs[0][0]) == 4);
        for (size_t i = 1; i < noisyX.value->Coeffs.size(); ++i) {
            assert(div_rounded(noisyX.value->Coeffs[0][i]) == 0);
        }
    }
    {
        std::shared_ptr<const SlotRing> slotRing = P257TestParameters();
        Context context(15,
            { 36028797017456641, 36028797014704129, 36028797014573057, 36028797014376449, 36028797013327873,
            36028797013000193, 36028797012606977, 36028797010444289, 36028797009985537, 36028797005856769,
            36028797005529089, 36028797005135873, 36028797003694081, 36028797003563009, 36028797001138177 },
            { 72057594037338113 }, slotRing->Prime(), 3.2);
        KeyGenerator keygen(&context);
        std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
        SecretKey sk(*tmp.first);
        PublicKey pk(*tmp.second);
        RelinearizationKey rk(*keygen.GenRelinearizationKey(&sk, 1));
        PkEncryptor encryptor(&context, &pk);
        Evaluator evaluator(&context, new EvaluationKey(&rk, nullptr));

        std::vector<uint64_t> data = { 12 };
        data.resize(slotRing->N());
        Plaintext xPlain(data, context.MaxLevel());
        evaluator.lightEncoder->ScaleUp(&xPlain, &xPlain);

        Ciphertext xEnc(&context, 1, context.MaxLevel());
        encryptor.Encrypt(&xPlain, &xEnc);

        poly evaluationElementFake;
        evaluationElementFake.resize(slotRing->SlotRank());
        Bootstrapper bootstrapper(context, slotRing,
            std::make_unique<P127PolyEvaluator, const SlotRing &, poly, poly, size_t>(*slotRing,
            std::move(evaluationElementFake), { 1 }, 8));

        Context bootstrappingContext(bootstrapper.BootstrappingContext());

        SecretKey bootstrappingSk(sk);
        bootstrapper.CreateSecretKey(sk, bootstrappingSk);
        BootstrappingKey bk;
        bootstrapper.CreateBootstrappingKey(sk, bk, true);

        Ciphertext noisyEncX(&bootstrappingContext, 1, bootstrappingContext.MaxLevel());
        bootstrapper.HomomorphicNoisyDecrypt(xEnc, bk, noisyEncX);

        Decryptor decryptor(&bootstrappingContext, &bootstrappingSk);

        Plaintext noisyX(&bootstrappingContext, bootstrappingContext.MaxLevel());
        decryptor.Decrypt(&noisyEncX, &noisyX);
        bootstrapper.BootstrappingEvaluator().lightEncoder->ScaleDown(&noisyX, &noisyX);

        auto div_rounded = [&slotRing](uint64_t x) {
            return (x + (slotRing->R().scalarMod / slotRing->Prime() / 2)) % slotRing->R().scalarMod /
                (slotRing->R().scalarMod / slotRing->Prime());
        };
        assert(div_rounded(noisyX.value->Coeffs[0][0]) == 12);
        for (size_t i = 1; i < noisyX.value->Coeffs.size(); ++i) {
            assert(div_rounded(noisyX.value->Coeffs[0][i]) == 0);
        }
    }
    std::cout << "TestHomomorphicNoisyDecrypt(): success" << std::endl;
}
/*
 * @brief 测试低位提取功能
 *
 */
void TestSlotwiseDigitExtract()
{
    std::shared_ptr<const SlotRing> slotRing = P127TestParameters();
    std::unique_ptr<PolyEvaluator> digitExtractor = P127TestParametersDigitExtractor(*slotRing);
    Context context(15,
        { 36028797017456641, 36028797014704129, 36028797014573057, 36028797014376449, 36028797013327873,
        36028797013000193, 36028797012606977, 36028797010444289, 36028797009985537, 36028797005856769,
        36028797005529089, 36028797005135873, 36028797003694081, 36028797003563009, 36028797001138177 },
        { 72057594037338113 }, slotRing->Prime(), 3.2);

    KeyGenerator keygen(&context);
    std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
    SecretKey sk(*tmp.first);
    PublicKey pk(*tmp.second);

    poly data;
    PolyAdd(data, slotRing->FromSlotValue({ 5 * 127 * 127 + 2 * 127 - 7 * 127 }, 0), slotRing->R().scalarMod);
    PolyAdd(data, slotRing->FromSlotValue({ 111 * 127 * 127 - 8 * 127 + 5 * 127 }, 63), slotRing->R().scalarMod);
    Plaintext xPlain(data, context.MaxLevel());

    Bootstrapper bootstrapper(context, slotRing, std::move(digitExtractor));

    Context bootstrapping_context = bootstrapper.BootstrappingContext();

    SecretKey bootstrappingSk(sk);
    bootstrapper.CreateSecretKey(sk, bootstrappingSk);
    KeyGenerator bootstrapping_keygen(&bootstrapping_context);
    PublicKey bootstrappingPk = *bootstrapping_keygen.GenPublicKey(&bootstrappingSk);
    RelinearizationKey rk(*bootstrapping_keygen.GenRelinearizationKey(&bootstrappingSk, 1));
    PkEncryptor encryptor(&bootstrapping_context, &bootstrappingPk);
    Evaluator bootstrappingEvaluator(&bootstrapping_context, new EvaluationKey(&rk, nullptr));

    bootstrappingEvaluator.lightEncoder->ScaleUp(&xPlain, &xPlain);
    Ciphertext xEnc(&bootstrapping_context, 1, bootstrapping_context.MaxLevel());
    encryptor.Encrypt(&xPlain, &xEnc);

    BootstrappingKey bk;
    bootstrapper.CreateBootstrappingKey(sk, bk, true);

    Ciphertext resultEnc(&context, 1, context.MaxLevel());
    bootstrapper.SlotwiseDigitExtract(xEnc, bk, resultEnc);

    Decryptor decryptor(&context, &sk);
    Plaintext result(&context, context.MaxLevel());
    decryptor.Decrypt(&resultEnc, &result);
    bootstrapper.contextChain.GetEvaluator(0).lightEncoder->ScaleDown(&result, &result);

    SlotRing result_slot_ring = slotRing->ChangeExponent(1);

    poly resultPoly;
    for (int i = 0; i < result.CoeffCount(); i++) {
        resultPoly.push_back(result.value->Coeffs[0][i]);
    }
    resultPoly.resize(result_slot_ring.N());
    poly expected;
    PolyAdd(expected, result_slot_ring.FromSlotValue({ 5 }, 0), result_slot_ring.R().scalarMod);
    PolyAdd(expected, result_slot_ring.FromSlotValue({ 111 }, 63), result_slot_ring.R().scalarMod);

    assert(resultPoly == expected);
    std::cout << "TestSlotwiseDigitExtract(): success" << std::endl;
}
/*
 * @brief 测试线性变换功能
 *
 */
void TestCoeffsToSlots()
{
    std::shared_ptr<const SlotRing> slotRing = P257TestParameters();
    Context context(15,
        { 36028797017456641, 36028797014704129, 36028797014573057, 36028797014376449, 36028797013327873,
        36028797013000193, 36028797012606977, 36028797010444289, 36028797009985537, 36028797005856769,
        36028797005529089, 36028797005135873, 36028797003694081, 36028797003563009, 36028797001138177 },
        { 72057594037338113 }, slotRing->Prime(), 3.2);

    KeyGenerator keygen(&context);
    std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
    SecretKey sk(*tmp.first);

    std::vector<uint64_t> data;
    data.resize(slotRing->N());
    data[0] = 4;
    data[256] = 12;
    data[128] = 3;
    data[257] = 7;
    Plaintext xPlain(data, context.MaxLevel());

    poly evaluationElementFake;
    evaluationElementFake.resize(slotRing->SlotRank());
    Bootstrapper bootstrapper(context, slotRing,
        std::make_unique<P127PolyEvaluator, const SlotRing &, poly, poly, size_t>(*slotRing,
        std::move(evaluationElementFake), { 1 }, 8));
    bootstrapper.Initialize();

    Context bootstrapping_context = bootstrapper.BootstrappingContext();

    SecretKey bootstrappingSk(sk);
    bootstrapper.CreateSecretKey(sk, bootstrappingSk);
    KeyGenerator bootstrapping_keygen(&bootstrapping_context);
    PublicKey bootstrapping_pk = *bootstrapping_keygen.GenPublicKey(&bootstrappingSk);
    PkEncryptor encryptor(&bootstrapping_context, &bootstrapping_pk);

    Ciphertext xEnc(&bootstrapping_context, 1, bootstrapping_context.MaxLevel());

    bootstrapper.contextChain.TargetEvaluator().lightEncoder->ScaleUp(&xPlain, &xPlain);

    encryptor.Encrypt(&xPlain, &xEnc);

    BootstrappingKey bk;
    bootstrapper.CreateBootstrappingKey(sk, bk, true);

    Ciphertext noisyEncX(&bootstrapping_context, 1, bootstrapping_context.MaxLevel());
    bootstrapper.CoeffsToSlots(xEnc, bk, noisyEncX);

    Decryptor decryptor(&bootstrapping_context, &bootstrappingSk);

    Plaintext noisyX(&bootstrapping_context, bootstrapping_context.MaxLevel());
    decryptor.Decrypt(&noisyEncX, &noisyX);
    bootstrapper.contextChain.TargetEvaluator().lightEncoder->ScaleDown(&noisyX, &noisyX);

    poly resultPoly;
    for (int i = 0; i < noisyX.CoeffCount(); i++) {
        resultPoly.push_back(noisyX.value->Coeffs[0][i]);
    }
    resultPoly.resize(slotRing->N());

    assert(slotRing->ExtractSlotValue(resultPoly, 0)[0] == 4);
    assert(slotRing->ExtractSlotValue(resultPoly, 1)[0] == 12);
    for (size_t i = 2; i < slotRing->SlotGroupLen(); ++i) {
        assert(IsZero(slotRing->ExtractSlotValue(resultPoly, i)));
    }

    std::cout << "TestCoeffsToSlots(): success" << std::endl;
}
/*
 * @brief 测试整体自举功能，主要流程如下
 * 1、将明文进行编码到密文上
 * 2、将密文执行24次平方增加密文的噪声（最多平方28次)
 * 3、对已经有较大噪声的密文进行自举
 * 4、对自举后的结果进行解密，再将密文平方查看还能进行多少次，结果为1平方正确，结果为其他值平方错误，
 */
void TestBootstrapping()
{
    std::cout << "            TestBootstrapping" << std::endl;
    std::shared_ptr<SlotRing> slotRing = P257TestParameters();
    SlotRing basicSlotRing = slotRing->ChangeExponent(1);

    Context context(15,
        { 36028797017456641, 36028797014704129, 36028797014573057, 36028797014376449, 36028797013327873,
        36028797013000193, 36028797012606977, 36028797010444289, 36028797009985537, 36028797005856769,
        36028797005529089, 36028797005135873, 36028797003694081, 36028797003563009, 36028797001138177 },
        { 72057594037338113 }, slotRing->Prime(), 3.2);

    // set up keys
    KeyGenerator keygen(&context);
    std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
    SecretKey sk(*tmp.first);
    PublicKey pk(*tmp.second);
    RelinearizationKey rk(*keygen.GenRelinearizationKey(&sk, 1));
    Evaluator evaluator(&context, new EvaluationKey(&rk, nullptr));
    PkEncryptor encryptor(&context, &pk);
    Decryptor decryptor(&context, &sk);

    // create an example plaintext
    poly data;
    PolyAdd(data, basicSlotRing.FromSlotValue({ 1 }, 0), basicSlotRing.R().scalarMod);
    PolyAdd(data, basicSlotRing.FromSlotValue({ 3 }, 1), basicSlotRing.R().scalarMod);
    PolyAdd(data, basicSlotRing.FromSlotValue({ 5 }, 2), basicSlotRing.R().scalarMod);
    PolyAdd(data, basicSlotRing.FromSlotValue({ 7 }, 3), basicSlotRing.R().scalarMod);
    PolyAdd(data, basicSlotRing.FromSlotValue({ 23 }, 4), basicSlotRing.R().scalarMod);

    Plaintext xPlain{ data, context.MaxLevel() };

    Ciphertext xEnc(&context, 1, context.MaxLevel());
    // ------加密前要缩放t->q0-------
    evaluator.lightEncoder->ScaleUp(&xPlain, &xPlain);
    encryptor.Encrypt(&xPlain, &xEnc);
    std::cout << "encrypted message" << std::endl;

    for (size_t i = 0; i < 24; ++i) {
        Ciphertext cipherMult(&context, xEnc.Degree() + xEnc.Degree(), context.MaxLevel());
        evaluator.Mul(&xEnc, &xEnc, &cipherMult, MultiType::ciphertext);
        evaluator.Relinearize(&cipherMult, &xEnc);
    }

    std::cout << "performed computations" << std::endl;

    std::cout << "setup context" << std::endl;

    Bootstrapper bootstrapper(context, slotRing, P257TestParametersDigitExtractor(*slotRing));
    bootstrapper.Initialize();

    std::cout << "initialized bootstrapper" << std::endl;

    BootstrappingKey bk;
    bootstrapper.CreateBootstrappingKey(sk, bk);

    std::cout << "created bootstrapping key" << std::endl;

    auto start = std::chrono::steady_clock::now();

    Ciphertext inCoeffs(&context, 1, context.MaxLevel());
    bootstrapper.SlotsToCoeffs(xEnc, bk, inCoeffs);

    auto end = std::chrono::steady_clock::now();
    std::cout << "moved to coefficients in " <<
        std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms and " << kswitchCounter <<
        " key-switch operations" << std::endl;
    kswitchCounter = 0;
    start = end;

    Ciphertext noisyDec(&context, 1, context.MaxLevel());
    bootstrapper.HomomorphicNoisyDecrypt(inCoeffs, bk, noisyDec);

    end = std::chrono::steady_clock::now();
    std::cout << "homomorphically decrypted in " <<
        std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms and " << kswitchCounter <<
        " key-switch operations" << std::endl;
    start = end;
    kswitchCounter = 0;

    Ciphertext in_slots(&context, 1, context.MaxLevel());
    bootstrapper.CoeffsToSlots(noisyDec, bk, in_slots);

    end = std::chrono::steady_clock::now();
    std::cout << "moved to slots in " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() <<
        " ms and " << kswitchCounter << " key-switch operations" << std::endl;
    start = end;
    kswitchCounter = 0;

    Ciphertext digitExtracted(&context, 1, context.MaxLevel());
    bootstrapper.SlotwiseDigitExtract(in_slots, bk, digitExtracted);

    end = std::chrono::steady_clock::now();
    std::cout << "bootstrapped in " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() <<
        " ms and " << kswitchCounter << " key-switch operations" << std::endl;

    Plaintext result(&context, context.MaxLevel());
    decryptor.Decrypt(&digitExtracted, &result);
    evaluator.lightEncoder->ScaleDown(&result, &result);

    poly resultPoly;
    for (int i = 0; i < result.CoeffCount(); i++) {
        resultPoly.push_back(result.value->Coeffs[0][i]);
    }
    resultPoly.resize(basicSlotRing.N());
    std::cout << " ------乘24次后自举的结果----- " << std::endl;
    for (size_t i = 0; i < basicSlotRing.SlotGroupLen(); ++i) {
        std::cout << "i:" << i << ", " << basicSlotRing.ExtractSlotValue(resultPoly, i)[0] << std::endl;
    }

    for (size_t i = 0; i < 16; ++i) {
        Ciphertext cipherMult(&context, digitExtracted.Degree() + digitExtracted.Degree(), context.MaxLevel());
        evaluator.Mul(&digitExtracted, &digitExtracted, &cipherMult, MultiType::ciphertext);
        evaluator.Relinearize(&cipherMult, &digitExtracted);
        decryptor.Decrypt(&digitExtracted, &result);
        evaluator.lightEncoder->ScaleDown(&result, &result);
        std::cout << "再平方" << i + 1 << "次, " << basicSlotRing.ExtractSlotValue(result.value->Coeffs[0], 0)[0] <<
            std::endl;
    }
}

SlotwiseTrace::SlotwiseTrace(const SlotRing &slotRing, size_t sourceSubfieldIndexLog2, size_t targetSubfieldIndexLog2)
    : slotRing(slotRing),
      sourceSubfieldIndexLog2(sourceSubfieldIndexLog2),
      targetSubfieldIndexLog2(targetSubfieldIndexLog2)
{
    assert(targetSubfieldIndexLog2 > sourceSubfieldIndexLog2);
}

poly SlotwiseTrace::operator () (const poly &x) const
{
    poly current = x;
    poly copy;
    for (size_t i = Log2Exact(slotRing.SlotRank()) - targetSubfieldIndexLog2;
        i < Log2Exact(slotRing.SlotRank()) - sourceSubfieldIndexLog2; ++i) {
        copy = slotRing.Frobenius_(static_cast<size_t>(1) << i)(current);
        PolyAdd(current, copy, slotRing.R().scalarMod);
    }
    return current;
}
/*
 * @brief 对密文进行数字提取中的相关跟踪trace计算
 *
 * @param in 输入的密文
 * @param eval 对应参数的计算器
 * @param gk galois变换用到的密钥
 * @param destination 计算后的结果
 */
void SlotwiseTrace::ApplyCiphertext(Ciphertext &in, Evaluator &eval, GaloisKeys &gk, Ciphertext &destination) const
{
    destination.Copy(in.El());
    Ciphertext copy(eval.params, 1, eval.params->MaxLevel());
    for (size_t i = Log2Exact(slotRing.SlotRank()) - targetSubfieldIndexLog2;
        i < Log2Exact(slotRing.SlotRank()) - sourceSubfieldIndexLog2; ++i) {
        eval.ApplyGalois(&destination,
            static_cast<uint32_t>(ModExp(slotRing.Prime(), static_cast<size_t>(1) << i, slotRing.IndexMod())),
            gk.GetGaloisKey(
            static_cast<uint32_t>(ModExp(slotRing.Prime(), static_cast<size_t>(1) << i, slotRing.IndexMod()))),
            &copy);
        LogGalois();
        eval.Add(&destination, &copy, &destination);
    }
}

std::vector<uint32_t> SlotwiseTrace::GaloisElements() const
{
    std::vector<uint32_t> result;
    for (size_t i = Log2Exact(slotRing.SlotRank()) - targetSubfieldIndexLog2;
        i < Log2Exact(slotRing.SlotRank()) - sourceSubfieldIndexLog2; ++i) {
        result.push_back(static_cast<uint32_t>(ModExp(slotRing.Prime(), (size_t)1 << i, slotRing.IndexMod())));
    }
    return result;
}

size_t SlotwiseTrace::field_index() const
{
    return static_cast<size_t>(1) << (targetSubfieldIndexLog2 - sourceSubfieldIndexLog2);
}

P257CorrectionPolyEvaluator::P257CorrectionPolyEvaluator(const SlotRing &slotRing, poly evaluationElement,
    poly correctionPoly, size_t log2Exponent)
    : slotRing(slotRing),
      constantCorrection(0),
      log2Exponent(log2Exponent),
      normOp(slotRing, Log2Exact(slotRing.SlotRank()) - log2Exponent)
{
    if (evaluationElement.size() != slotRing.SlotRank()) {
        throw std::invalid_argument("Elements must have SlotRank() coefficients.");
    }
    poly slottedEvaluationElement;

    for (int i = 0; i < slotRing.SlotGroupLen(); i++) {
        PolyAdd(slottedEvaluationElement, slotRing.FromSlotValue(evaluationElement, i), slotRing.R().scalarMod);
    }
    this->evaluationElement = std::move(slottedEvaluationElement);

    if (correctionPoly.size() != 0) {
        constantCorrection = correctionPoly[0];
        for (size_t i = 1; i < correctionPoly.size(); ++i) {
            this->correctionPoly.push_back(correctionPoly[i]);
        }
    }
}

poly P257CorrectionPolyEvaluator::operator () (const poly &x) const
{
    throw std::invalid_argument("Unimplemented");
}

/*
 * @brief 对密文进行数字提取多项式的计算，特别针对明文模数p=257的情况
 *
 * 该函数实现了以下步骤:
 * 1. 将评估元素evaluationElement转换为明文多项式
 * 2. 计算(evaluationElement - in)的范数，用于修正delta值
 * 3. 应用校正多项式的非常数部分
 * 4. 执行密文乘法运算
 * 5. 添加校正多项式的常数项
 *
 * 在BFV方案中，这个函数用于自举过程中的数字提取步骤，将密文从高位模数降至低位模数。
 *
 * @param in 输入的密文，包含需要进行数字提取的数据
 * @param context BFV方案的上下文参数，包含明文模数等信息
 * @param eval 同态运算评估器，用于执行密文上的基本运算
 * @param gk Galois密钥，用于执行自同态运算
 * @param destination 输出参数，存储计算结果的密文
 */
void P257CorrectionPolyEvaluator::ApplyCiphertext(Ciphertext &in, Context &context, Evaluator &eval, GaloisKeys &gk,
    Ciphertext &destination) const
{
    const uint64_t &plainModulus = context.t;
    Plaintext evaluationElementApply(this->evaluationElement, context.MaxLevel());

    for (int i = 0; i < this->evaluationElement.size(); i++) {
        evaluationElementApply.value->Coeffs[0][i] = this->evaluationElement[i] % plainModulus;
    }

    // 计算(evaluationElement - in)的范数norm，这是修正delta的结果
    Ciphertext tmp(&context, 1, context.MaxLevel());

    eval.lightEncoder->ScaleUp(&evaluationElementApply, &evaluationElementApply);
    eval.Sub(&in, &evaluationElementApply, &tmp);
    eval.Neg(&tmp, &tmp);

    normOp.ApplyCiphertext(tmp, eval, gk, destination);

    // 计算校正的非常数部分
    NaiveAddPolyEvalInplace(destination, correctionPoly, eval);

    Ciphertext resultMult(eval.params, destination.Degree() + in.Degree(), eval.params->MaxLevel());

    eval.Mul(&destination, &in, &resultMult, MultiType::ciphertext);
    eval.Relinearize(&resultMult, &destination);
    LogRelin();

    vector<uint64_t> correctionVector;
    correctionVector.resize(eval.params->N());
    correctionVector[0] = constantCorrection % plainModulus; // reduce
    Plaintext correctionConstant(correctionVector, context.MaxLevel());

    eval.lightEncoder->ScaleUp(&correctionConstant, &correctionConstant);
    eval.Add(&destination, &correctionConstant, &destination);
}

std::vector<uint32_t> P257CorrectionPolyEvaluator::GaloisElements() const
{
    return normOp.GaloisElements();
}